<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>二分法的理解 | Daidaini的 个人博客</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta name="description" content="使用循环实现先看一道leetcode上的题：在排序数组中查找元素的第一个和最后一个位置 题目明确要求 实现的时间复杂度为 O(log n)。这个要求，很容易让我们联想到二分法这个算法。再拆解下题目描述，已经是有序数组，满足二分查找的前提，那么只需要通过二分法找到目标元素的位置，再向前后迭代获取最左和最右的索引即是题目所需要的答案。 列一下所实现的二分查找的代码： 12345678910111213">
<meta property="og:type" content="article">
<meta property="og:title" content="二分法的理解">
<meta property="og:url" content="https://daidaini.giteee.io/selfblog/2023/02/07/%E4%BA%8C%E5%88%86%E6%B3%95%E7%9A%84%E7%90%86%E8%A7%A3/index.html">
<meta property="og:site_name" content="Daidaini的 个人博客">
<meta property="og:description" content="使用循环实现先看一道leetcode上的题：在排序数组中查找元素的第一个和最后一个位置 题目明确要求 实现的时间复杂度为 O(log n)。这个要求，很容易让我们联想到二分法这个算法。再拆解下题目描述，已经是有序数组，满足二分查找的前提，那么只需要通过二分法找到目标元素的位置，再向前后迭代获取最左和最右的索引即是题目所需要的答案。 列一下所实现的二分查找的代码： 12345678910111213">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2023-02-06T16:00:00.000Z">
<meta property="article:modified_time" content="2023-02-09T02:35:51.269Z">
<meta property="article:author" content="Daidaini">
<meta property="article:tag" content="数据结构与算法">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/selfblog/atom.xml" title="Daidaini的 个人博客" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/selfblog/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/selfblog/css/style.css">

  
    
<link rel="stylesheet" href="/selfblog/fancybox/jquery.fancybox.min.css">

  
<meta name="generator" content="Hexo 6.3.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/selfblog/" id="logo">Daidaini的 个人博客</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/selfblog/">Home</a>
        
          <a class="main-nav-link" href="/selfblog/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/selfblog/atom.xml" title="RSS 订阅"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="搜索"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="搜索"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="https://daidaini.giteee.io/selfblog"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main"><article id="post-二分法的理解" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/selfblog/2023/02/07/%E4%BA%8C%E5%88%86%E6%B3%95%E7%9A%84%E7%90%86%E8%A7%A3/" class="article-date">
  <time class="dt-published" datetime="2023-02-06T16:00:00.000Z" itemprop="datePublished">2023-02-07</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/selfblog/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="p-name article-title" itemprop="headline name">
      二分法的理解
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h2 id="使用循环实现"><a href="#使用循环实现" class="headerlink" title="使用循环实现"></a>使用循环实现</h2><p>先看一道leetcode上的题：<br><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/">在排序数组中查找元素的第一个和最后一个位置</a></p>
<p>题目明确要求 实现的时间复杂度为 O(log n)。这个要求，很容易让我们联想到二分法这个算法。<br>再拆解下题目描述，已经是有序数组，满足二分查找的前提，那么只需要通过二分法找到目标元素的位置，再向前后迭代获取最左和最右的索引即是题目所需要的答案。</p>
<p>列一下所实现的二分查找的代码：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//只返回查找到的位置，不确定是最左或最右</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">BinarySearch</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; nums, <span class="type">int</span> target)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="built_in">assert</span>(nums.<span class="built_in">size</span>() &gt;= <span class="number">2</span>);</span><br><span class="line">	<span class="type">int</span> left = <span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> right = nums.<span class="built_in">size</span>() - <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">while</span> (left &lt;= right)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="type">int</span> mid = (right + left) / <span class="number">2</span>;</span><br><span class="line">		<span class="type">int</span> midval = nums[mid];</span><br><span class="line">		<span class="keyword">if</span> (midval &lt; target) <span class="comment">//往右折</span></span><br><span class="line">		&#123;</span><br><span class="line">			left = mid + <span class="number">1</span>;	<span class="comment">//由于left &lt;= mid ，所以要确保left右移需要加1</span></span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (midval &gt; target) <span class="comment">//往左折</span></span><br><span class="line">		&#123;</span><br><span class="line">			right = mid - <span class="number">1</span>;	<span class="comment">//由于mid&lt;right, 必会使right左移，但这里mid已经检查过一遍，最差情况会导致再检查一次，</span></span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">return</span> mid;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>代码理解:</p>
<ul>
<li>二分查找需要确定区间，每次折半，所以需要定义左右端点位置 left、right</li>
<li>在循环内逐步缩小区间，结束区间的条件定为 left&lt;&#x3D;right，意为在left&#x3D;&#x3D;right还要进行一次判断，该值是不是target目标值</li>
<li>折半查找，需要定义mid位置，mid &#x3D; (right+left)&#x2F;2，这样做的话，在left&lt;right时，必然会有mid&lt;right，mid&gt;&#x3D;left条件的成立</li>
<li>将mid位置的值与target进行比较，三种情况分别处理。<ul>
<li>相等则返回，表示已查找到</li>
<li>中值小于target值，表示target值在右区间，需要将left端点右移，left &#x3D; mid+1，需要加1，这样的最极端情况是left&#x3D;&#x3D;right，循环后再判断一次即可</li>
<li>中值大于target值，表示target值在左区间，需要将right端点左移，right &#x3D; mid-1，减1，这样的最极端情况是left&#x3D;&#x3D;mid的时候，这种情况的时候表示无法左移了，那么right&#x3D;&#x3D;mid-1&#x3D;&#x3D;left-1，会退出循环，也是不存在遗漏查找的情况</li>
<li>默认返回-1，表示查找不到；如果查找到，会直接在循环中就返回</li>
</ul>
</li>
</ul>
<p>值得注意的是，如果代码如上，那么mid &#x3D; (right+left)&#x2F;2 和 mid &#x3D; (right+left+1)&#x2F;2 两种情况的处理没有区别。  </p>
<h2 id="使用递归实现"><a href="#使用递归实现" class="headerlink" title="使用递归实现"></a>使用递归实现</h2><p>依然通过leetcode上一个题来举例：<br><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/">搜索旋转排序数组 II</a><br>旋转后的数组是没法保证折半之后左右区间都是肯定满足左区间的数小于等于右区间的数的<br>忽略一些细节的判断，我们可以简单的在折半之后两边都进行查找，这样的话，使用递归方法来实现会使代码简单直观很多。  </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">BinarySearch</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; nums, <span class="type">int</span> target, <span class="type">int</span> left, <span class="type">int</span> right)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (left &gt; right)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="type">int</span> mid = (left + right) / <span class="number">2</span>;</span><br><span class="line">	<span class="type">int</span> midval = nums[mid];</span><br><span class="line">	<span class="keyword">if</span> (midval == target)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> mid;</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">	<span class="type">int</span> result = <span class="built_in">BinarySearch</span>(nums, target, mid + <span class="number">1</span>, right);</span><br><span class="line">	<span class="keyword">if</span> (result != <span class="number">-1</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> result;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="built_in">BinarySearch</span>(nums, target, left, mid - <span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>然后简但调用就可以达到查找的目的</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">bool</span> <span class="title">search</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; nums, <span class="type">int</span> target)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">BinarySearch</span>(nums, target, <span class="number">0</span>, nums.<span class="built_in">size</span>() - <span class="number">1</span>) != <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>二分折半的思想是共通的，注意临界点的情况即可。</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="https://daidaini.giteee.io/selfblog/2023/02/07/%E4%BA%8C%E5%88%86%E6%B3%95%E7%9A%84%E7%90%86%E8%A7%A3/" data-id="cldwhn3uw00007cs142oncjye" data-title="二分法的理解" class="article-share-link">分享</a>
      
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/selfblog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" rel="tag">数据结构与算法</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/selfblog/2023/02/09/%E5%9B%9E%E8%B0%83%E5%87%BD%E6%95%B0%E7%9A%84%E7%90%86%E8%A7%A3/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">前一篇</strong>
      <div class="article-nav-title">
        
          回调函数的理解
        
      </div>
    </a>
  
  
    <a href="/selfblog/2023/01/31/%E6%8C%87%E9%92%88%E7%9A%84%E7%90%86%E8%A7%A3/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">后一篇</strong>
      <div class="article-nav-title">C指针的理解</div>
    </a>
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">分类</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/selfblog/categories/C-11/">C++11</a></li><li class="category-list-item"><a class="category-list-link" href="/selfblog/categories/C-%E7%BC%96%E7%A8%8B/">C++编程</a></li><li class="category-list-item"><a class="category-list-link" href="/selfblog/categories/Linux%E7%B3%BB%E7%BB%9F/">Linux系统</a></li><li class="category-list-item"><a class="category-list-link" href="/selfblog/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/">操作系统</a></li><li class="category-list-item"><a class="category-list-link" href="/selfblog/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">标签</h3>
    <div class="widget">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/selfblog/tags/C-%E5%AD%A6%E4%B9%A0/" rel="tag">C++学习</a></li><li class="tag-list-item"><a class="tag-list-link" href="/selfblog/tags/C-%E6%A0%87%E5%87%86%E5%BA%93/" rel="tag">C++标准库</a></li><li class="tag-list-item"><a class="tag-list-link" href="/selfblog/tags/C-%E7%89%B9%E6%80%A7/" rel="tag">C++特性</a></li><li class="tag-list-item"><a class="tag-list-link" href="/selfblog/tags/C%E8%AF%AD%E8%A8%80/" rel="tag">C语言</a></li><li class="tag-list-item"><a class="tag-list-link" href="/selfblog/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" rel="tag">操作系统</a></li><li class="tag-list-item"><a class="tag-list-link" href="/selfblog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" rel="tag">数据结构与算法</a></li><li class="tag-list-item"><a class="tag-list-link" href="/selfblog/tags/%E7%AC%94%E8%AE%B0/" rel="tag">笔记</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">标签云</h3>
    <div class="widget tagcloud">
      <a href="/selfblog/tags/C-%E5%AD%A6%E4%B9%A0/" style="font-size: 10px;">C++学习</a> <a href="/selfblog/tags/C-%E6%A0%87%E5%87%86%E5%BA%93/" style="font-size: 20px;">C++标准库</a> <a href="/selfblog/tags/C-%E7%89%B9%E6%80%A7/" style="font-size: 20px;">C++特性</a> <a href="/selfblog/tags/C%E8%AF%AD%E8%A8%80/" style="font-size: 10px;">C语言</a> <a href="/selfblog/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" style="font-size: 10px;">操作系统</a> <a href="/selfblog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" style="font-size: 10px;">数据结构与算法</a> <a href="/selfblog/tags/%E7%AC%94%E8%AE%B0/" style="font-size: 20px;">笔记</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">归档</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/selfblog/archives/2023/02/">二月 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/selfblog/archives/2023/01/">一月 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/selfblog/archives/2022/03/">三月 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/selfblog/archives/2021/09/">九月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/selfblog/archives/2021/07/">七月 2021</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">最新文章</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/selfblog/2023/02/09/%E5%9B%9E%E8%B0%83%E5%87%BD%E6%95%B0%E7%9A%84%E7%90%86%E8%A7%A3/">回调函数的理解</a>
          </li>
        
          <li>
            <a href="/selfblog/2023/02/07/%E4%BA%8C%E5%88%86%E6%B3%95%E7%9A%84%E7%90%86%E8%A7%A3/">二分法的理解</a>
          </li>
        
          <li>
            <a href="/selfblog/2023/01/31/%E6%8C%87%E9%92%88%E7%9A%84%E7%90%86%E8%A7%A3/">C指针的理解</a>
          </li>
        
          <li>
            <a href="/selfblog/2023/01/31/%E7%90%86%E8%A7%A3CPP%E7%9A%84%E7%A7%BB%E5%8A%A8%E8%AF%AD%E4%B9%89/">理解CPP的移动语义</a>
          </li>
        
          <li>
            <a href="/selfblog/2022/03/23/%E5%B8%B8%E7%94%A8Linux%E5%91%BD%E4%BB%A4/">常用Linux命令</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2023 Daidaini<br>
      Powered by <a href="https://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/selfblog/" class="mobile-nav-link">Home</a>
  
    <a href="/selfblog/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    


<script src="/selfblog/js/jquery-3.4.1.min.js"></script>



  
<script src="/selfblog/fancybox/jquery.fancybox.min.js"></script>




<script src="/selfblog/js/script.js"></script>





  </div>
</body>
</html>